package java_bin_tree.search_tree;

import java.util.NoSuchElementException;

/**
 * 普通的二分搜索树
 * 基于整形的二分搜索树
 */
public class BST {
    private class TreeNode{
        private int val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;

        }
    }
    private int size;//当前节点个数
    private TreeNode root;//根节点
    public void add(int val){
        root=add(root,val);
    }

    /**
     * 查找：判断val是否存在于当前二叉树中
     * @param val
     * @return
     */
    public boolean contains(int val){
        return contains(root,val);
    }

    /**
     * 判断当前以root为根的BST中是否包含val
     * @param root
     * @param val
     * @return
     */
    private boolean contains(TreeNode root, int val) {
       //边界
        if(root==null){
            return false;
        }
        if(root.val==val){
            return true;
        }else if(val<root.val){
            //递归在左树中查找
            return contains(root.left,val);
        }else{
            //递归在右树中查找
            return contains(root.right,val);
        }
    }
    //查找最小值
    public int findMin(){
        //判空
        if(size==0){
            //空树
            throw new NoSuchElementException("BST is empty!cannot find min");
        }
        TreeNode minNode=minNode(root);
        return minNode.val;
    }

    /**
     * 在当前以root为根的BST中找最小值所在节点，返回最小值节点
     * @param root
     * @return
     */
    private TreeNode minNode(TreeNode root) {
        if(root.left==null){
            //说明此时root就是最小值
            return root;
        }
        return minNode(root.left);//否则像左子树中找最小值
    }
    public int findMax(){
        if(size==0){
            throw new NoSuchElementException("BST is empty!cannot find max");
        }
        TreeNode maxNode=maxNode(root);
        return maxNode.val;
    }

    /**
     * 查询以root为根的BST中最大值节点
     * @param root
     * @return
     */
    private TreeNode maxNode(TreeNode root) {
        if(root.right==null){
            return root;
        }
        return maxNode(root.right);
    }

    /**
     * 在当前BST中删除最小值节点，返回删除的最小值
     * @return
     */
    public int removeMin(){
        int min=findMin();//找到最小值
        root=removeMin(root);
        return min;
    }

    /**
     * 在当前以root为根的BST中删除最小值所在节点，返回删除后的树根
     * @param root
     * @return
     */
    private TreeNode removeMin(TreeNode root) {
        if(root.left==null){
            //当前root就是待删除结点
            TreeNode right=root.right;//获取到root的右子树
            root=root.right=null;//root为null是此节点直接删除，root.right为空是断线
            size--;
            return right;//把右子树返回了
        }
        //递归去左子树中删除
        root.left=removeMin(root.left);//左子树中删除:删完后返回的根节点给root.left是更新左子树的树根（将28与22建立联系了）
        return root;//返回更新后的根节点root
    }

public int removeMax(){
        int max=findMax();
        root=removeMax(root);
        return max;
}

    /**
     * 在当前以root为根的BST中删除最大值节点，返回删除后的树根
     * @param root
     * @return
     */
    private TreeNode removeMax(TreeNode root) {
        if(root.right==null){
            TreeNode left=root.left;//获取到root的左子树
            root=root.left=null;
            size--;
            return left;
        }
        root.right=removeMax(root.right);
        return root;
    }
    public void remove(int val){
        root=remove(root,val);
    }

    /**
     * 在当前以root为根节点的BST中删除值为val的节点
     * 返回删除后的新的根节点
     * @param root
     * @param val
     * @return
     */
    private TreeNode remove(TreeNode root, int val) {
        //边界
        if(root==null){
            //把树中所有节点都遍历完还没有找到值为val的节点，就不存在值为val的节点
            throw new NoSuchElementException("BST中没有值为"+val+"的节点");
        }else if(val<root.val){
            //此时待删除节点位于左子树
            root.left=remove(root.left,val);
            return root;
        }else if(val>root.val){
            root.right=remove(root.right,val);
            return root;
        }else{
            //此时root.val==val,root就是待删除节点
            if(root.left==null){
                //只有右孩子，返回右孩子即可（跟删最小值一样）
                TreeNode right=root.right;
                root=root.right=null;
                size--;
                return right;
            }
            if(root.right==null){
                //只有左孩子（和删最大值一样）
                TreeNode left=root.left;
                root=root.left=null;
                size--;
                return left;
            }
            //此时root.left和root.right都不为空
            //Hibbard Deletion:找到前驱或者后继节点，这里找后继
            TreeNode successor=minNode(root.right);//在右子树中找后继节点（即在右子树中找最小值节点）
            successor.right=removeMin(root.right);//把右子树中最小的这个successor59先删除，删除后用successor.right拼接右子树
            //为什么没size--:因为removeMin删除操作里已经有了【即在右子树中删除后继节点的时候已经size--了】
            //然后拼接左子树
            successor.left=root.left;
            root.left=root.right=root=null;//将本身待删除的root的left和right置空同时root置空删除节点
            return successor;//返回后继
        }

    }

    /**
     * 向以root为根的BST中插入一个新的节点val
     * @param root
     * @param val
     * @return
     */
    private TreeNode add(TreeNode root, int val) {
        //创建新节点
        TreeNode newNode=new TreeNode(val);
        if(root==null){
            //当前值就是根节点
            size++;
            return newNode;
        }
        if(val<root.val){
            //左树中插入
            root.left=add(root.left,val);
        }
        if(val>root.val){
            root.right=add(root.right,val);
        }
        return root;
    }
    public String toString(){
        StringBuilder sb=new StringBuilder();
        generateBSTString(root,0,sb);//先序遍历打印，0是树的高度
        return sb.toString();
    }

    /**
     * 先序遍历以root为根的BST，将节点值存储在sb中
     * @param root
     * @param height
     * @param sb
     */
    private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
        //边界
        if(root==null){
            sb.append(generateHeightString(height)).append("NULL\n");
            return;
        }
        //先打印根节点，记得“--”打印，而不是sb.append(root.val).append("\n");
        sb.append(generateHeightString(height)).append(root.val).append("\n");
        //递归访问左子树
        generateBSTString(root.left,height+1,sb);
        //递归访问右子树
        generateBSTString(root.right,height+1,sb);
    }

    /**
     * 按当前所处的树的层次打印“--”
     * 每多一层，就多两个“--”
     * @param height
     * @return
     */
    private String generateHeightString(int height) {
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < height; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
}
